package datastructure.Graph;

import java.util.Arrays;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/30 21:15
 */
public class DijkstraPath {

    public static int[] getLatestPath(AdjacencyList graph, int no) {
        int len = graph.getVertexNums();
        int[] dist = new int[ len ];//表示当前已经找到的从v0到每个终点vi的最短路径
        int[] path = new int[ len ];//表示上一个顶点，即需要经过的顶点
        boolean[] set = new boolean[ len ];//已经被并入最短路径的顶点
        int nums = 1;

        for (int i = 0; i < len; i++) {
            if (i == no) {
                dist[ i ] = 0;
                set[ i ] = true;
            } else {
                dist[ i ] = Integer.MAX_VALUE;
                path[ i ] = -1;
                set[ i ] = false;
            }
        }

        VNode[] nodes = graph.getNodes();
        VNode node = nodes[ no ];
        int dists = Integer.MAX_VALUE;
        int tempNo = no;

        while (nums < len) {
            AceNode firstAce = node.firstAce;
            int nodeNo, weight;
            if (firstAce != null) {
                nodeNo = firstAce.vNode.nodeNo;
                weight = firstAce.weight;
                if (dist[ nodeNo ] == Integer.MAX_VALUE || weight + dist[ nodeNo ] < dist[ nodeNo ]) {
                    dist[ nodeNo ] = weight + dist[ nodeNo ];
                    path[ nodeNo ] = node.nodeNo;
                }
            }
            AceNode nextAce = firstAce.nextAce;
            while (nextAce != null) {
                nodeNo = nextAce.vNode.nodeNo;
                weight = nextAce.weight;
                if (dist[ nodeNo ] == Integer.MAX_VALUE || weight + dist[ nodeNo ] < dist[ nodeNo ]) {
                    dist[ nodeNo ] = weight + dist[ nodeNo ];
                    path[ nodeNo ] = node.nodeNo;
                }
                nextAce = nextAce.nextAce;
            }
            for (int i = 0; i < len; i++) {
                if (i != no && !set[ i ] && dist[ i ] < dists) {
                    dists = dist[ i ];
                    tempNo = i;
                }
            }
            path[ tempNo ] = node.nodeNo;
            set[ tempNo ] = true;
            node = nodes[ tempNo ];
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] matrix = {{0, 2, 0, 0, 5, 0}, {0, 0, 7, 0, 1, 0}, {0, 0, 0, 4, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 2, 0, 0, 0}, {0, 0, 0, 6, 3, 0}};
        AdjacencyList adjustList = AdjacencyList.createAdjustList(matrix);
        int[] latestPath = getLatestPath(adjustList, 0);
        System.out.println(Arrays.toString(latestPath));
    }

}
